A router is usually designed to perform one or more basic networking tasks. One basic networking task is the classification of network data traffic packets received at the router. Packet classification involves determining a received packet's flow based on a source and/or destination address, and the flow label or some higher level information, such as transport ports.
Typically, a packet received at a router is forwarded to a processor and is assigned to a packet editor. The packet editor runs multiple “jump condition” instructions until it finds a match with a particular set of bits in the packet header. The processor subsequently extracts a classification key and a forwarding key from the packet. Using the result of the classification, the packet is typically stamped with a class of service. In addition, as a result of the forwarding key, the packet headers are changed to reflect the new forwarding information.
One problem with typical packet processing is that when the packet is received at the processor the packet header is matched against many compare statements in order to find which routine the program is to jump to in order to process this unique packet. Consequently, if there are more than one thousand types of packets to process, program space for one thousand unique comparison instructions is typically required and a binary search with a minimum of log2 (1000) comparisons and as many jump statements will be required.
Moreover, each comparison may take up to two to three processor cycles to process and each jump statement may take two processor cycles to process. As a result, having to compare numerous packet types may require significant waiting time before a packet is processed or require significant processing power to process all the packets at the rate they are received.
Another problem with typical packet processing occurs if a new service is to be provided for the router. To add new service to an exemplary router, the router memory has to be reprogrammed and modified. As a result, the router has to be shut down for the new service to be added. It is not desirable to shut down an active router that is currently serving customers.
Further, once the router is restarted, the new service has to be tested along with all the old services to ensure that no errors have been induced into the old services. If the new program has, for example, over one million services in total, it is not efficient to take the time to send multiple packets of each of the one million services to test all aspects of the new program.